package leetcode_100;

/**
 *@author 周杨
 *DecodeWays_91 输入一个字符串 只会出现整数  其中1到26分别代表一个解码 判断能有多少种解码组合
 *describe:题目叙述不清 0的边界值问题有错误
 	动归数组解决 每次判断该位置的数是否可以组合纳入 是否可以单独纳入 AC 74% 每次保存能单独录入 和组合录入的情况总数
 *2018年5月18日 下午4:57:21
 */
public class DecodeWays_91 {

	public static void main(String[] args) {
		DecodeWays_91 test=new DecodeWays_91();
		System.out.println(test.numDecodings("0"));//0
		System.out.println(test.numDecodings("226"));//3
		System.out.println(test.numDecodings("10"));//1
		System.out.println(test.numDecodings("0"));//0
		System.out.println(test.numDecodings("01"));//0
		System.out.println(test.numDecodings("101"));//1
		System.out.println(test.numDecodings("110"));//1
		System.out.println(test.numDecodings("1010"));//1
		System.out.println(test.numDecodings("1212"));//5
		System.out.println(test.numDecodings("1"));//1
		// 0 100 010 01为什么是0  101 -2

	}
	public int numDecodings1(String s) {
		boolean flag=false;//用来判断前一个数是否能够组合
		int res;
        if(s.charAt(0)=='0') 
        	return 0;
        res=1;
        for(int i=1;i<s.length();++i) {
        	char pre=s.charAt(i-1);
        	char now=s.charAt(i);
        	if(now=='0'){
                if(pre=='0'||pre>'2')//不可组合
                    return 0;
                if((pre>'0'&&pre<'2')||(pre=='2'&&now<='6')){
                	if(flag) {//可以组合 则取掉一个组合
                		--res;
                	}
        		    continue;
                }
            }
        	if(pre==0) {//01这种
        		flag=false;
        		continue;
        	}
        	if((pre>'0'&&pre<'2')||(pre=='2'&&now<='6')) {//此时不为0 并且可以和以前组合
        		++res;
        		flag=true;
        	}
        }
        return res;
    }
	
	
	
	/**
	 * describe: 题目有问题 10 竟然得到1 100 答案竟是0
	 * 2018年5月18日 下午4:54:52
	 */
	/*public int numDecodings(String s) {
		int res;
		boolean flag=false;
        if(s.charAt(0)=='0') {
        	res=0;
        	flag=true;
        }
        else {
        	res=1;
        }
        for(int i=1;i<s.length();++i) {
        	char pre=s.charAt(i-1);
        	char now=s.charAt(i);
        	if(flag) {
        		if(now!='0') {//没有出现过除0以外的数字 此时出现了
        			flag=false;
        			++res;
        			continue;
        		}
        	}
        	if(now=='0'&&((pre>'0'&&pre<'2')||(pre=='2'&&now<='6'))) {//此时为0 以前的可以组合
        		res*=2;
        		continue;
        	}
        	if((pre>'0'&&pre<'2')||(pre=='2'&&now<='6'))//此时不为0 并且可以和以前组合
        		++res;
        }
        return res;
    }*/
	
	
	/**
	 * describe: 动归数组解决 每次判断该位置的数是否可以组合纳入 是否可以单独纳入 AC 74%
	 * 2018年5月18日 下午4:57:11
	 */
	public int numDecodings(String s) {
        if(s == null || s.length() == 0) {
          return 0;
      }
      int n = s.length();
      int firstDp=1;//保存如果merge 则i-2之前的结果
      int secondDp=s.charAt(0) != '0' ? 1 : 0;
      int res=secondDp;
      for(int i = 1; i < n; i++) {
          char now = s.charAt(i);
          char before = s.charAt(i-1);
          res=0;
          if(now!='0') {//可以单独纳入
        	 res+=secondDp;
          }
          if((before>'0'&&before<'2')||(before=='2'&&now<='6')) {//可以组合并入
        	 res+=firstDp;
          }
          firstDp=secondDp;
          secondDp=res;
      }
      return res;
      //return dp[n];
  }

}
